<html><!-- Created using the cpp_pretty_printer from the dlib C++ library.  See http://dlib.net for updates. --><head><title>dlib C++ Library - binary_search_tree_kernel_2.h</title></head><body bgcolor='white'><pre>
<font color='#009900'>// Copyright (C) 2003  Davis E. King (davis@dlib.net)
</font><font color='#009900'>// License: Boost Software License   See LICENSE.txt for the full license.
</font><font color='#0000FF'>#ifndef</font> DLIB_BINARY_SEARCH_TREE_KERNEl_2_
<font color='#0000FF'>#define</font> DLIB_BINARY_SEARCH_TREE_KERNEl_2_

<font color='#0000FF'>#include</font> "<a style='text-decoration:none' href='binary_search_tree_kernel_abstract.h.html'>binary_search_tree_kernel_abstract.h</a>"
<font color='#0000FF'>#include</font> "<a style='text-decoration:none' href='../algs.h.html'>../algs.h</a>"
<font color='#0000FF'>#include</font> "<a style='text-decoration:none' href='../interfaces/map_pair.h.html'>../interfaces/map_pair.h</a>"
<font color='#0000FF'>#include</font> "<a style='text-decoration:none' href='../interfaces/enumerable.h.html'>../interfaces/enumerable.h</a>"
<font color='#0000FF'>#include</font> "<a style='text-decoration:none' href='../interfaces/remover.h.html'>../interfaces/remover.h</a>"
<font color='#0000FF'>#include</font> "<a style='text-decoration:none' href='../serialize.h.html'>../serialize.h</a>"
<font color='#0000FF'>#include</font> <font color='#5555FF'>&lt;</font>functional<font color='#5555FF'>&gt;</font>

<font color='#0000FF'>namespace</font> dlib 
<b>{</b>

    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare <font color='#5555FF'>=</font> std::less<font color='#5555FF'>&lt;</font>domain<font color='#5555FF'>&gt;</font>
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'>class</font> <b><a name='binary_search_tree_kernel_2'></a>binary_search_tree_kernel_2</b> : <font color='#0000FF'>public</font> enumerable<font color='#5555FF'>&lt;</font>map_pair<font color='#5555FF'>&lt;</font>domain,range<font color='#5555FF'>&gt;</font> <font color='#5555FF'>&gt;</font>,
                                        <font color='#0000FF'>public</font> asc_pair_remover<font color='#5555FF'>&lt;</font>domain,range,compare<font color='#5555FF'>&gt;</font>
    <b>{</b>

        <font color='#009900'>/*!
            INITIAL VALUE
                NIL == pointer to a node that represents a leaf
                tree_size == 0
                tree_root == NIL     
                at_start == true
                current_element == 0


            CONVENTION
                current_element_valid() == (current_element != 0)
                if (current_element_valid()) then
                    element() == current_element-&gt;d and current_element-&gt;r
                at_start_ == at_start()


                tree_size   == size()

                NIL == pointer to a node that represents a leaf

                if (tree_size != 0)
                    tree_root == pointer to the root node of the binary search tree
                else
                    tree_root == NIL

                tree_root-&gt;color == black                    
                Every leaf is black and all leafs are the NIL node.
                The number of black nodes in any path from the root to a leaf is the 
                same. 

                for all nodes:
                {
                    - left points to the left subtree or NIL if there is no left subtree  
                    - right points to the right subtree or NIL if there is no right 
                      subtree                                                             
                    - parent points to the parent node or NIL if the node is the root     
                    - ordering of nodes is determined by comparing each node's d member  
                    - all elements in a left subtree are &lt;= the node                      
                    - all elements in a right subtree are &gt;= the node                     
                    - color == red or black                                               
                    - if (color == red)                                                   
                        - the node's children are black
                }

        !*/</font>
    
        <font color='#0000FF'>class</font> <b><a name='node'></a>node</b>
        <b>{</b>
        <font color='#0000FF'>public</font>:            
            node<font color='#5555FF'>*</font> left;
            node<font color='#5555FF'>*</font> right;
            node<font color='#5555FF'>*</font> parent;
            domain d;
            range r;
            <font color='#0000FF'><u>char</u></font> color;
        <b>}</b>;

        <font color='#0000FF'>class</font> <b><a name='mpair'></a>mpair</b> : <font color='#0000FF'>public</font> map_pair<font color='#5555FF'>&lt;</font>domain,range<font color='#5555FF'>&gt;</font>
        <b>{</b>
        <font color='#0000FF'>public</font>:
            <font color='#0000FF'>const</font> domain<font color='#5555FF'>*</font> d;
            range<font color='#5555FF'>*</font> r;

            <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> <b><a name='key'></a>key</b><font face='Lucida Console'>(</font> 
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font> <b>{</b> <font color='#0000FF'>return</font> <font color='#5555FF'>*</font>d; <b>}</b>

            <font color='#0000FF'>const</font> range<font color='#5555FF'>&amp;</font> <b><a name='value'></a>value</b><font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font> <b>{</b> <font color='#0000FF'>return</font> <font color='#5555FF'>*</font>r; <b>}</b>

            range<font color='#5555FF'>&amp;</font> <b><a name='value'></a>value</b><font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font> <b>{</b> <font color='#0000FF'>return</font> <font color='#5555FF'>*</font>r; <b>}</b>
        <b>}</b>;
        
     
        <font color='#0000FF'>const</font> <font color='#0000FF'>static</font> <font color='#0000FF'><u>char</u></font> red <font color='#5555FF'>=</font> <font color='#979000'>0</font>;
        <font color='#0000FF'>const</font> <font color='#0000FF'>static</font> <font color='#0000FF'><u>char</u></font> black <font color='#5555FF'>=</font> <font color='#979000'>1</font>;


        <font color='#0000FF'>public</font>:

            <font color='#0000FF'>typedef</font> domain domain_type;
            <font color='#0000FF'>typedef</font> range range_type;
            <font color='#0000FF'>typedef</font> compare compare_type;
            <font color='#0000FF'>typedef</font> mem_manager mem_manager_type;

            <b><a name='binary_search_tree_kernel_2'></a>binary_search_tree_kernel_2</b><font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font> :
                NIL<font face='Lucida Console'>(</font>pool.allocate<font face='Lucida Console'>(</font><font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>,
                tree_size<font face='Lucida Console'>(</font><font color='#979000'>0</font><font face='Lucida Console'>)</font>,
                tree_root<font face='Lucida Console'>(</font>NIL<font face='Lucida Console'>)</font>,
                current_element<font face='Lucida Console'>(</font><font color='#979000'>0</font><font face='Lucida Console'>)</font>,
                at_start_<font face='Lucida Console'>(</font><font color='#979000'>true</font><font face='Lucida Console'>)</font>
            <b>{</b>
                NIL<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                NIL<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> <font color='#979000'>0</font>;
                NIL<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> <font color='#979000'>0</font>;
                NIL<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> <font color='#979000'>0</font>;
            <b>}</b>

            <font color='#0000FF'>virtual</font> ~<b><a name='binary_search_tree_kernel_2'></a>binary_search_tree_kernel_2</b><font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font>; 
    
            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>void</u></font> <b><a name='clear'></a>clear</b><font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font>;

            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>short</u></font> <b><a name='height'></a>height</b> <font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;

            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> <b><a name='count'></a>count</b> <font face='Lucida Console'>(</font>
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;

            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>void</u></font> <b><a name='add'></a>add</b> <font face='Lucida Console'>(</font>
                domain<font color='#5555FF'>&amp;</font> d,
                range<font color='#5555FF'>&amp;</font> r
            <font face='Lucida Console'>)</font>;

            <font color='#0000FF'><u>void</u></font> <b><a name='remove'></a>remove</b> <font face='Lucida Console'>(</font>
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d,
                domain<font color='#5555FF'>&amp;</font> d_copy,
                range<font color='#5555FF'>&amp;</font> r
            <font face='Lucida Console'>)</font>;

            <font color='#0000FF'><u>void</u></font> <b><a name='destroy'></a>destroy</b> <font face='Lucida Console'>(</font>
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
            <font face='Lucida Console'>)</font>;

            <font color='#0000FF'><u>void</u></font> <b><a name='remove_any'></a>remove_any</b> <font face='Lucida Console'>(</font>
                domain<font color='#5555FF'>&amp;</font> d,
                range<font color='#5555FF'>&amp;</font> r
            <font face='Lucida Console'>)</font>;

            <font color='#0000FF'>inline</font> <font color='#0000FF'>const</font> range<font color='#5555FF'>*</font> <b><a name='operator'></a>operator</b>[] <font face='Lucida Console'>(</font>
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> item
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;

            <font color='#0000FF'>inline</font> range<font color='#5555FF'>*</font> <b><a name='operator'></a>operator</b>[] <font face='Lucida Console'>(</font>
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> item
            <font face='Lucida Console'>)</font>;

            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>void</u></font> <b><a name='swap'></a>swap</b> <font face='Lucida Console'>(</font>
                binary_search_tree_kernel_2<font color='#5555FF'>&amp;</font> item
            <font face='Lucida Console'>)</font>;

            <font color='#009900'>// functions from the enumerable interface
</font>            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>size_t</u></font> <b><a name='size'></a>size</b> <font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;

            <font color='#0000FF'><u>bool</u></font> <b><a name='at_start'></a>at_start</b> <font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;

            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>void</u></font> <b><a name='reset'></a>reset</b> <font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;

            <font color='#0000FF'><u>bool</u></font> <b><a name='current_element_valid'></a>current_element_valid</b> <font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;

            <font color='#0000FF'>const</font> map_pair<font color='#5555FF'>&lt;</font>domain,range<font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> <b><a name='element'></a>element</b> <font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;

            map_pair<font color='#5555FF'>&lt;</font>domain,range<font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> <b><a name='element'></a>element</b> <font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font>;

            <font color='#0000FF'><u>bool</u></font> <b><a name='move_next'></a>move_next</b> <font face='Lucida Console'>(</font>
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;

            <font color='#0000FF'><u>void</u></font> <b><a name='remove_last_in_order'></a>remove_last_in_order</b> <font face='Lucida Console'>(</font>
                domain<font color='#5555FF'>&amp;</font> d,
                range<font color='#5555FF'>&amp;</font> r
            <font face='Lucida Console'>)</font>;

            <font color='#0000FF'><u>void</u></font> <b><a name='remove_current_element'></a>remove_current_element</b> <font face='Lucida Console'>(</font>
                domain<font color='#5555FF'>&amp;</font> d,
                range<font color='#5555FF'>&amp;</font> r
            <font face='Lucida Console'>)</font>;

            <font color='#0000FF'><u>void</u></font> <b><a name='position_enumerator'></a>position_enumerator</b> <font face='Lucida Console'>(</font>
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;

        <font color='#0000FF'>private</font>:

            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>void</u></font> <b><a name='rotate_left'></a>rotate_left</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - t != NIL 
                    - t-&gt;right != NIL
                ensures
                    - performs a left rotation around t and its right child
            !*/</font>

            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>void</u></font> <b><a name='rotate_right'></a>rotate_right</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - t != NIL 
                    - t-&gt;left != NIL
                ensures
                    - performs a right rotation around t and its left child
            !*/</font>

            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>void</u></font> <b><a name='double_rotate_right'></a>double_rotate_right</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - t != NIL 
                    - t-&gt;left != NIL 
                    - t-&gt;left-&gt;right != NIL 
                    - double_rotate_right() is only called in fix_after_add()
                ensures
                    - performs a left rotation around t-&gt;left 
                    - then performs a right rotation around t
            !*/</font>

            <font color='#0000FF'>inline</font> <font color='#0000FF'><u>void</u></font> <b><a name='double_rotate_left'></a>double_rotate_left</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - t != NIL 
                    - t-&gt;right != NIL 
                    - t-&gt;right-&gt;left != NIL 
                    - double_rotate_left() is only called in fix_after_add()
                ensures
                    - performs a right rotation around t-&gt;right 
                    - then performs a left rotation around t
            !*/</font>

            <font color='#0000FF'><u>void</u></font> <b><a name='remove_biggest_element_in_tree'></a>remove_biggest_element_in_tree</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t,
                domain<font color='#5555FF'>&amp;</font> d,
                range<font color='#5555FF'>&amp;</font> r
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - t != NIL  (i.e. there must be something in the tree to remove)
                ensures
                    - the biggest node in t has been removed 
                    - the biggest node element in t has been put into #d and #r 
                    - #t is still a binary search tree 
            !*/</font>

            <font color='#0000FF'><u>bool</u></font> <b><a name='remove_least_element_in_tree'></a>remove_least_element_in_tree</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t,
                domain<font color='#5555FF'>&amp;</font> d,
                range<font color='#5555FF'>&amp;</font> r
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - t != NIL  (i.e. there must be something in the tree to remove)
                ensures
                    - the least node in t has been removed 
                    - the least node element in t has been put into #d and #r 
                    - #t is still a binary search tree 
                    - if (the node that was removed was the one pointed to by current_element) then
                        - returns true
                    - else
                        - returns false
            !*/</font>

            <font color='#0000FF'><u>void</u></font> <b><a name='add_to_tree'></a>add_to_tree</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t,
                domain<font color='#5555FF'>&amp;</font> d,
                range<font color='#5555FF'>&amp;</font> r
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - t != NIL
                ensures
                    - d and r are now in #t
                    - there is a mapping from d to r in #t
                    - #d and #r have initial values for their types
                    - #t is still a binary search tree 
            !*/</font>

            <font color='#0000FF'><u>void</u></font> <b><a name='remove_from_tree'></a>remove_from_tree</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t,
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d,
                domain<font color='#5555FF'>&amp;</font> d_copy,
                range<font color='#5555FF'>&amp;</font> r
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - return_reference(t,d) != 0
                ensures
                    - #d_copy is equivalent to d                                     
                    - the first element in t equivalent to d that is encountered when searching down the tree
                      from t has been removed and swapped into #d_copy.  Also, the associated range element 
                      has been removed and swapped into #r.
                    - if (the node that got removed wasn't current_element) then
                        - adjusts the current_element pointer if the data in the node that it points to gets moved.
                    - else
                        - the value of current_element is now invalid
                    - #t is still a binary search tree 
            !*/</font>

            <font color='#0000FF'><u>void</u></font> <b><a name='remove_from_tree'></a>remove_from_tree</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t,
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - return_reference(t,d) != 0
                ensures                                  
                    - an element in t equivalent to d has been removed                
                    - #t is still a binary search tree 
            !*/</font>

            <font color='#0000FF'>const</font> range<font color='#5555FF'>*</font> <b><a name='return_reference'></a>return_reference</b> <font face='Lucida Console'>(</font>
                <font color='#0000FF'>const</font> node<font color='#5555FF'>*</font> t,
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;
            <font color='#009900'>/*!
                ensures
                    - if (there is a domain element equivalent to d in t) then
                        - returns a pointer to the element in the range equivalent to d
                    - else
                        - returns 0
            !*/</font>

            range<font color='#5555FF'>*</font> <b><a name='return_reference'></a>return_reference</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t,
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                ensures
                    - if (there is a domain element equivalent to d in t) then
                        - returns a pointer to the element in the range equivalent to d
                    - else
                        - returns 0
            !*/</font>

            <font color='#0000FF'><u>void</u></font> <b><a name='fix_after_add'></a>fix_after_add</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - t == pointer to the node just added
                    - t-&gt;color == red 
                    - t-&gt;parent != NIL (t must not be the root)
                    - fix_after_add() is only called after a new node has been added
                      to t
                ensures
                    - fixes any deviations from the CONVENTION caused by adding a node
            !*/</font>

            <font color='#0000FF'><u>void</u></font> <b><a name='fix_after_remove'></a>fix_after_remove</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - t == pointer to the only child of the node that was spliced out 
                    - fix_after_remove() is only called after a node has been removed
                      from t
                    - the color of the spliced out node was black
                ensures
                    - fixes any deviations from the CONVENTION causes by removing a node
            !*/</font>            


            <font color='#0000FF'><u>short</u></font> <b><a name='tree_height'></a>tree_height</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;
            <font color='#009900'>/*!
                ensures
                    - returns the number of nodes in the longest path from the root of the 
                      tree to a leaf
            !*/</font>

            <font color='#0000FF'><u>void</u></font> <b><a name='delete_tree'></a>delete_tree</b> <font face='Lucida Console'>(</font>
                node<font color='#5555FF'>*</font> t
            <font face='Lucida Console'>)</font>;
            <font color='#009900'>/*!
                requires
                    - t == root of binary search tree
                    - t != NIL
                ensures
                    - deletes all nodes in t except for NIL
            !*/</font>

            <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> <b><a name='get_count'></a>get_count</b> <font face='Lucida Console'>(</font>
                <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> item,
                node<font color='#5555FF'>*</font> tree_root
            <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>;
            <font color='#009900'>/*!
                requires
                    - tree_root == the root of a binary search tree or NIL
                ensures
                    - if (tree_root == NIL) then
                        - returns 0
                    - else
                        - returns the number of elements in tree_root that are 
                          equivalent to item
            !*/</font>



            <font color='#009900'>// data members
</font>            <font color='#0000FF'>typename</font> mem_manager::<font color='#0000FF'>template</font> rebind<font color='#5555FF'>&lt;</font>node<font color='#5555FF'>&gt;</font>::other pool;
            node<font color='#5555FF'>*</font> NIL;
            <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> tree_size;
            node<font color='#5555FF'>*</font> tree_root;
            <font color='#0000FF'>mutable</font> node<font color='#5555FF'>*</font> current_element;
            <font color='#0000FF'>mutable</font> <font color='#0000FF'><u>bool</u></font> at_start_;
            <font color='#0000FF'>mutable</font> mpair p;
            compare comp;

            

            <font color='#009900'>// restricted functions
</font>            <b><a name='binary_search_tree_kernel_2'></a>binary_search_tree_kernel_2</b><font face='Lucida Console'>(</font>binary_search_tree_kernel_2<font color='#5555FF'>&amp;</font><font face='Lucida Console'>)</font>;        
            binary_search_tree_kernel_2<font color='#5555FF'>&amp;</font> <b><a name='operator'></a>operator</b><font color='#5555FF'>=</font><font face='Lucida Console'>(</font>binary_search_tree_kernel_2<font color='#5555FF'>&amp;</font><font face='Lucida Console'>)</font>;


    <b>}</b>;

    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>   
    <font color='#0000FF'>inline</font> <font color='#0000FF'><u>void</u></font> <b><a name='swap'></a>swap</b> <font face='Lucida Console'>(</font>
        binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> a, 
        binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> b 
    <font face='Lucida Console'>)</font> <b>{</b> a.<font color='#BB00BB'>swap</font><font face='Lucida Console'>(</font>b<font face='Lucida Console'>)</font>; <b>}</b>



    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>   
    <font color='#0000FF'><u>void</u></font> <b><a name='deserialize'></a>deserialize</b> <font face='Lucida Console'>(</font>
        binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> item, 
        std::istream<font color='#5555FF'>&amp;</font> in
    <font face='Lucida Console'>)</font>
    <b>{</b>
        <font color='#0000FF'>try</font>
        <b>{</b>
            item.<font color='#BB00BB'>clear</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
            <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> size;
            <font color='#BB00BB'>deserialize</font><font face='Lucida Console'>(</font>size,in<font face='Lucida Console'>)</font>;
            domain d;
            range r;
            <font color='#0000FF'>for</font> <font face='Lucida Console'>(</font><font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> i <font color='#5555FF'>=</font> <font color='#979000'>0</font>; i <font color='#5555FF'>&lt;</font> size; <font color='#5555FF'>+</font><font color='#5555FF'>+</font>i<font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#BB00BB'>deserialize</font><font face='Lucida Console'>(</font>d,in<font face='Lucida Console'>)</font>;
                <font color='#BB00BB'>deserialize</font><font face='Lucida Console'>(</font>r,in<font face='Lucida Console'>)</font>;
                item.<font color='#BB00BB'>add</font><font face='Lucida Console'>(</font>d,r<font face='Lucida Console'>)</font>;
            <b>}</b>
        <b>}</b>
        <font color='#0000FF'>catch</font> <font face='Lucida Console'>(</font>serialization_error<font color='#5555FF'>&amp;</font> e<font face='Lucida Console'>)</font>
        <b>{</b> 
            item.<font color='#BB00BB'>clear</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
            <font color='#0000FF'>throw</font> <font color='#BB00BB'>serialization_error</font><font face='Lucida Console'>(</font>e.info <font color='#5555FF'>+</font> "<font color='#CC0000'>\n   while deserializing object of type binary_search_tree_kernel_2</font>"<font face='Lucida Console'>)</font>; 
        <b>}</b>
    <b>}</b>




<font color='#009900'>// ----------------------------------------------------------------------------------------
</font><font color='#009900'>// ----------------------------------------------------------------------------------------
</font>    <font color='#009900'>// member function definitions
</font><font color='#009900'>// ----------------------------------------------------------------------------------------
</font><font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    ~<b><a name='binary_search_tree_kernel_2'></a>binary_search_tree_kernel_2</b> <font face='Lucida Console'>(</font>
    <font face='Lucida Console'>)</font>
    <b>{</b>     
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>tree_root <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
            <font color='#BB00BB'>delete_tree</font><font face='Lucida Console'>(</font>tree_root<font face='Lucida Console'>)</font>;
        pool.<font color='#BB00BB'>deallocate</font><font face='Lucida Console'>(</font>NIL<font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='clear'></a>clear</b> <font face='Lucida Console'>(</font>
    <font face='Lucida Console'>)</font>
    <b>{</b>
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>tree_size <font color='#5555FF'>&gt;</font> <font color='#979000'>0</font><font face='Lucida Console'>)</font>
        <b>{</b>
            <font color='#BB00BB'>delete_tree</font><font face='Lucida Console'>(</font>tree_root<font face='Lucida Console'>)</font>;
            tree_root <font color='#5555FF'>=</font> NIL;
            tree_size <font color='#5555FF'>=</font> <font color='#979000'>0</font>;
        <b>}</b>
        <font color='#009900'>// reset the enumerator
</font>        <font color='#BB00BB'>reset</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>size_t</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='size'></a>size</b> <font face='Lucida Console'>(</font>
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#0000FF'>return</font> tree_size;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>short</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='height'></a>height</b> <font face='Lucida Console'>(</font>
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#0000FF'>return</font> <font color='#BB00BB'>tree_height</font><font face='Lucida Console'>(</font>tree_root<font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='count'></a>count</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> item
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#0000FF'>return</font> <font color='#BB00BB'>get_count</font><font face='Lucida Console'>(</font>item,tree_root<font face='Lucida Console'>)</font>;        
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='add'></a>add</b> <font face='Lucida Console'>(</font>
        domain<font color='#5555FF'>&amp;</font> d,
        range<font color='#5555FF'>&amp;</font> r
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>tree_size <font color='#5555FF'>=</font><font color='#5555FF'>=</font> <font color='#979000'>0</font><font face='Lucida Console'>)</font>
        <b>{</b>
            tree_root <font color='#5555FF'>=</font> pool.<font color='#BB00BB'>allocate</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
            tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
            tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> NIL;
            tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> NIL;
            tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> NIL;
            <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d,d<font face='Lucida Console'>)</font>;
            <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r,r<font face='Lucida Console'>)</font>;
        <b>}</b>
        <font color='#0000FF'>else</font> 
        <b>{</b>
            <font color='#BB00BB'>add_to_tree</font><font face='Lucida Console'>(</font>tree_root,d,r<font face='Lucida Console'>)</font>;
        <b>}</b>
        <font color='#5555FF'>+</font><font color='#5555FF'>+</font>tree_size;
        <font color='#009900'>// reset the enumerator
</font>        <font color='#BB00BB'>reset</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='remove'></a>remove</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d,
        domain<font color='#5555FF'>&amp;</font> d_copy,
        range<font color='#5555FF'>&amp;</font> r
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        <font color='#BB00BB'>remove_from_tree</font><font face='Lucida Console'>(</font>tree_root,d,d_copy,r<font face='Lucida Console'>)</font>;
        <font color='#5555FF'>-</font><font color='#5555FF'>-</font>tree_size;
        <font color='#009900'>// reset the enumerator
</font>        <font color='#BB00BB'>reset</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='destroy'></a>destroy</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> item
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        <font color='#BB00BB'>remove_from_tree</font><font face='Lucida Console'>(</font>tree_root,item<font face='Lucida Console'>)</font>;
        <font color='#5555FF'>-</font><font color='#5555FF'>-</font>tree_size;
        <font color='#009900'>// reset the enumerator
</font>        <font color='#BB00BB'>reset</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='remove_any'></a>remove_any</b> <font face='Lucida Console'>(</font>
        domain<font color='#5555FF'>&amp;</font> d,
        range<font color='#5555FF'>&amp;</font> r
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        <font color='#BB00BB'>remove_least_element_in_tree</font><font face='Lucida Console'>(</font>tree_root,d,r<font face='Lucida Console'>)</font>;
        <font color='#5555FF'>-</font><font color='#5555FF'>-</font>tree_size;
        <font color='#009900'>// reset the enumerator
</font>        <font color='#BB00BB'>reset</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    range<font color='#5555FF'>*</font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='operator'></a>operator</b>[] <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        <font color='#0000FF'>return</font> <font color='#BB00BB'>return_reference</font><font face='Lucida Console'>(</font>tree_root,d<font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'>const</font> range<font color='#5555FF'>*</font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='operator'></a>operator</b>[] <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#0000FF'>return</font> <font color='#BB00BB'>return_reference</font><font face='Lucida Console'>(</font>tree_root,d<font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='swap'></a>swap</b> <font face='Lucida Console'>(</font>
        binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> item
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        pool.<font color='#BB00BB'>swap</font><font face='Lucida Console'>(</font>item.pool<font face='Lucida Console'>)</font>;
        
        <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>p,item.p<font face='Lucida Console'>)</font>;
        <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>comp,item.comp<font face='Lucida Console'>)</font>;

        node<font color='#5555FF'>*</font> tree_root_temp            <font color='#5555FF'>=</font> item.tree_root;
        <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> tree_size_temp    <font color='#5555FF'>=</font> item.tree_size;
        node<font color='#5555FF'>*</font> <font color='#0000FF'>const</font> NIL_temp            <font color='#5555FF'>=</font> item.NIL;
        node<font color='#5555FF'>*</font> current_element_temp      <font color='#5555FF'>=</font> item.current_element;
        <font color='#0000FF'><u>bool</u></font> at_start_temp              <font color='#5555FF'>=</font> item.at_start_;
        
        item.tree_root                  <font color='#5555FF'>=</font> tree_root;
        item.tree_size                  <font color='#5555FF'>=</font> tree_size;
        item.NIL                        <font color='#5555FF'>=</font> NIL;
        item.current_element            <font color='#5555FF'>=</font> current_element;
        item.at_start_                  <font color='#5555FF'>=</font> at_start_;
        
        tree_root                       <font color='#5555FF'>=</font> tree_root_temp;
        tree_size                       <font color='#5555FF'>=</font> tree_size_temp;
        NIL                             <font color='#5555FF'>=</font> NIL_temp;
        current_element                 <font color='#5555FF'>=</font> current_element_temp;
        at_start_                       <font color='#5555FF'>=</font> at_start_temp;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='remove_last_in_order'></a>remove_last_in_order</b> <font face='Lucida Console'>(</font>
        domain<font color='#5555FF'>&amp;</font> d,
        range<font color='#5555FF'>&amp;</font> r
    <font face='Lucida Console'>)</font>
    <b>{</b>
        <font color='#BB00BB'>remove_biggest_element_in_tree</font><font face='Lucida Console'>(</font>tree_root,d,r<font face='Lucida Console'>)</font>;
        <font color='#5555FF'>-</font><font color='#5555FF'>-</font>tree_size;
        <font color='#009900'>// reset the enumerator
</font>        <font color='#BB00BB'>reset</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='remove_current_element'></a>remove_current_element</b> <font face='Lucida Console'>(</font>
        domain<font color='#5555FF'>&amp;</font> d,
        range<font color='#5555FF'>&amp;</font> r
    <font face='Lucida Console'>)</font>
    <b>{</b>
        node<font color='#5555FF'>*</font> t <font color='#5555FF'>=</font> current_element;
        <font color='#BB00BB'>move_next</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
        <font color='#BB00BB'>remove_from_tree</font><font face='Lucida Console'>(</font>t,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d,d,r<font face='Lucida Console'>)</font>;
        <font color='#5555FF'>-</font><font color='#5555FF'>-</font>tree_size;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='position_enumerator'></a>position_enumerator</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#009900'>// clear the enumerator state and make sure the stack is empty
</font>        <font color='#BB00BB'>reset</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
        at_start_ <font color='#5555FF'>=</font> <font color='#979000'>false</font>;
        node<font color='#5555FF'>*</font> t <font color='#5555FF'>=</font> tree_root;
        node<font color='#5555FF'>*</font> parent <font color='#5555FF'>=</font> NIL;
        <font color='#0000FF'><u>bool</u></font> went_left <font color='#5555FF'>=</font> <font color='#979000'>false</font>;
        <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
        <b>{</b>
            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font> <font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>d , t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d <font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// if item is on the left then look in left
</font>                parent <font color='#5555FF'>=</font> t;
                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
                went_left <font color='#5555FF'>=</font> <font color='#979000'>true</font>;
            <b>}</b>
            <font color='#0000FF'>else</font> <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font><font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d , d<font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// if item is on the right then look in right
</font>                parent <font color='#5555FF'>=</font> t;
                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
                went_left <font color='#5555FF'>=</font> <font color='#979000'>false</font>;
            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>
                current_element <font color='#5555FF'>=</font> t;
                <font color='#0000FF'>return</font>;
            <b>}</b>
        <b>}</b>

        <font color='#009900'>// if we didn't find any matches but there might be something after the
</font>        <font color='#009900'>// d in this tree.
</font>        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>parent <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
        <b>{</b>
            current_element <font color='#5555FF'>=</font> parent;
            <font color='#009900'>// if we went left from this node then this node is the next
</font>            <font color='#009900'>// biggest.
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>went_left<font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#0000FF'>return</font>;
            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>
                <font color='#BB00BB'>move_next</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
            <b>}</b>
        <b>}</b>
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font><font color='#009900'>// ----------------------------------------------------------------------------------------
</font>    <font color='#009900'>// enumerable function definitions
</font><font color='#009900'>// ----------------------------------------------------------------------------------------
</font><font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='at_start'></a>at_start</b> <font face='Lucida Console'>(</font>
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#0000FF'>return</font> at_start_;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='reset'></a>reset</b> <font face='Lucida Console'>(</font>
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        at_start_ <font color='#5555FF'>=</font> <font color='#979000'>true</font>;
        current_element <font color='#5555FF'>=</font> <font color='#979000'>0</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='current_element_valid'></a>current_element_valid</b> <font face='Lucida Console'>(</font>
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#0000FF'>return</font> <font face='Lucida Console'>(</font>current_element <font color='#5555FF'>!</font><font color='#5555FF'>=</font> <font color='#979000'>0</font><font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'>const</font> map_pair<font color='#5555FF'>&lt;</font>domain,range<font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='element'></a>element</b> <font face='Lucida Console'>(</font>
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        p.d <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font><font face='Lucida Console'>(</font>current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d<font face='Lucida Console'>)</font>;
        p.r <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font><font face='Lucida Console'>(</font>current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r<font face='Lucida Console'>)</font>;
        <font color='#0000FF'>return</font> p;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    map_pair<font color='#5555FF'>&lt;</font>domain,range<font color='#5555FF'>&gt;</font><font color='#5555FF'>&amp;</font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='element'></a>element</b> <font face='Lucida Console'>(</font>
    <font face='Lucida Console'>)</font>
    <b>{</b>
        p.d <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font><font face='Lucida Console'>(</font>current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d<font face='Lucida Console'>)</font>;
        p.r <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font><font face='Lucida Console'>(</font>current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r<font face='Lucida Console'>)</font>;
        <font color='#0000FF'>return</font> p;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='move_next'></a>move_next</b> <font face='Lucida Console'>(</font>
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#009900'>// if we haven't started iterating yet
</font>        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>at_start_<font face='Lucida Console'>)</font>
        <b>{</b>
            at_start_ <font color='#5555FF'>=</font> <font color='#979000'>false</font>;
            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>tree_size <font color='#5555FF'>=</font><font color='#5555FF'>=</font> <font color='#979000'>0</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#0000FF'>return</font> <font color='#979000'>false</font>;
            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>
                <font color='#009900'>// find the first element in the tree
</font>                current_element <font color='#5555FF'>=</font> tree_root;
                node<font color='#5555FF'>*</font> temp <font color='#5555FF'>=</font> current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
                <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font>temp <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                <b>{</b>
                    current_element <font color='#5555FF'>=</font> temp;
                    temp <font color='#5555FF'>=</font> current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
                <b>}</b>
                <font color='#0000FF'>return</font> <font color='#979000'>true</font>;
            <b>}</b>
        <b>}</b>
        <font color='#0000FF'>else</font>
        <b>{</b>
            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>current_element <font color='#5555FF'>=</font><font color='#5555FF'>=</font> <font color='#979000'>0</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#0000FF'>return</font> <font color='#979000'>false</font>;
            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>
                <font color='#0000FF'><u>bool</u></font> went_up;  <font color='#009900'>// true if we went up the tree from a child node to parent
</font>                <font color='#0000FF'><u>bool</u></font> from_left <font color='#5555FF'>=</font> <font color='#979000'>false</font>; <font color='#009900'>// true if we went up and were coming from a left child node
</font>                <font color='#009900'>// find the next element in the tree
</font>                <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                <b>{</b>
                    <font color='#009900'>// go right and down                    
</font>                    current_element <font color='#5555FF'>=</font> current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
                    went_up <font color='#5555FF'>=</font> <font color='#979000'>false</font>;
                <b>}</b>
                <font color='#0000FF'>else</font>
                <b>{</b>
                    went_up <font color='#5555FF'>=</font> <font color='#979000'>true</font>;
                    node<font color='#5555FF'>*</font> parent <font color='#5555FF'>=</font> current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;
                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>parent <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                    <b>{</b>
                        <font color='#009900'>// in this case we have iterated over all the element of the tree
</font>                        current_element <font color='#5555FF'>=</font> <font color='#979000'>0</font>;
                        <font color='#0000FF'>return</font> <font color='#979000'>false</font>;
                    <b>}</b>

                    from_left <font color='#5555FF'>=</font> <font face='Lucida Console'>(</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> current_element<font face='Lucida Console'>)</font>;
                    <font color='#009900'>// go up to parent
</font>                    current_element <font color='#5555FF'>=</font> parent;
                <b>}</b>


                <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font><font color='#979000'>true</font><font face='Lucida Console'>)</font>
                <b>{</b>
                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>went_up<font face='Lucida Console'>)</font>
                    <b>{</b>
                        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>from_left<font face='Lucida Console'>)</font>
                        <b>{</b>
                            <font color='#009900'>// in this case we have found the next node
</font>                            <font color='#0000FF'>break</font>;
                        <b>}</b>
                        <font color='#0000FF'>else</font>
                        <b>{</b>
                            <font color='#009900'>// we should go up
</font>                            node<font color='#5555FF'>*</font> parent <font color='#5555FF'>=</font> current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;
                            from_left <font color='#5555FF'>=</font> <font face='Lucida Console'>(</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> current_element<font face='Lucida Console'>)</font>;                            
                            current_element <font color='#5555FF'>=</font> parent;
                            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>current_element <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                            <b>{</b>
                                <font color='#009900'>// in this case we have iterated over all the elements
</font>                                <font color='#009900'>// in the tree
</font>                                current_element <font color='#5555FF'>=</font> <font color='#979000'>0</font>;
                                <font color='#0000FF'>return</font> <font color='#979000'>false</font>;
                            <b>}</b>
                        <b>}</b>
                    <b>}</b>
                    <font color='#0000FF'>else</font>
                    <b>{</b>
                        <font color='#009900'>// we just went down to a child node
</font>                        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                        <b>{</b>
                            <font color='#009900'>// go left
</font>                            went_up <font color='#5555FF'>=</font> <font color='#979000'>false</font>;
                            current_element <font color='#5555FF'>=</font> current_element<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
                        <b>}</b>
                        <font color='#0000FF'>else</font>
                        <b>{</b>
                            <font color='#009900'>// if there is no left child then we have found the next node
</font>                            <font color='#0000FF'>break</font>;
                        <b>}</b>
                    <b>}</b>
                <b>}</b>

                <font color='#0000FF'>return</font> <font color='#979000'>true</font>;               
            <b>}</b>
        <b>}</b>
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font><font color='#009900'>// ----------------------------------------------------------------------------------------
</font>    <font color='#009900'>// private member function definitions
</font><font color='#009900'>// ----------------------------------------------------------------------------------------
</font><font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='delete_tree'></a>delete_tree</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t
    <font face='Lucida Console'>)</font>  
    <b>{</b>
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
            <font color='#BB00BB'>delete_tree</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font face='Lucida Console'>)</font>;
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
            <font color='#BB00BB'>delete_tree</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font face='Lucida Console'>)</font>;
        pool.<font color='#BB00BB'>deallocate</font><font face='Lucida Console'>(</font>t<font face='Lucida Console'>)</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='rotate_left'></a>rotate_left</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t
    <font face='Lucida Console'>)</font> 
    <b>{</b>

        <font color='#009900'>// perform the rotation
</font>        node<font color='#5555FF'>*</font> temp <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> temp<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>temp<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
            temp<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> t;
        temp<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> t;
        temp<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;


        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> tree_root<font face='Lucida Console'>)</font>
            tree_root <font color='#5555FF'>=</font> temp;
        <font color='#0000FF'>else</font> 
        <b>{</b>
            <font color='#009900'>// if t was on the left
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
                t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> temp;
            <font color='#0000FF'>else</font>
                t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> temp;
        <b>}</b>

        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> temp;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='rotate_right'></a>rotate_right</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        <font color='#009900'>// perform the rotation
</font>        node<font color='#5555FF'>*</font> temp <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> temp<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>temp<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
            temp<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> t;
        temp<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> t;
        temp<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;

        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> tree_root<font face='Lucida Console'>)</font>
            tree_root <font color='#5555FF'>=</font> temp;
        <font color='#0000FF'>else</font> 
        <b>{</b>
            <font color='#009900'>// if t is a left child
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
                t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> temp;
            <font color='#0000FF'>else</font>
                t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> temp;
        <b>}</b>

        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> temp;
    <b>}</b>


<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='double_rotate_right'></a>double_rotate_right</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t
    <font face='Lucida Console'>)</font>
    <b>{</b>

        <font color='#009900'>// preform the rotation
</font>        node<font color='#5555FF'>&amp;</font> temp <font color='#5555FF'>=</font> <font color='#5555FF'>*</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font face='Lucida Console'>)</font>;
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> temp.right;
        temp.right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> t;
        temp.left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> temp.parent;
        temp.parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> temp.left;
        temp.parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>temp;
        temp.right <font color='#5555FF'>=</font> t;
        temp.left <font color='#5555FF'>=</font> temp.parent;
        temp.parent <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;  


        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>tree_root <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
            tree_root <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>temp;
        <font color='#0000FF'>else</font>
        <b>{</b>
            <font color='#009900'>// t is a left child
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
                t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>temp;
            <font color='#0000FF'>else</font>
                t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>temp;
        <b>}</b>
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>temp;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='double_rotate_left'></a>double_rotate_left</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t
    <font face='Lucida Console'>)</font>
    <b>{</b>


        <font color='#009900'>// preform the rotation
</font>        node<font color='#5555FF'>&amp;</font> temp <font color='#5555FF'>=</font> <font color='#5555FF'>*</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font face='Lucida Console'>)</font>;
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> temp.left;
        temp.left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> t;
        temp.right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> temp.parent;
        temp.parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> temp.right;
        temp.parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>temp;
        temp.left <font color='#5555FF'>=</font> t;
        temp.right <font color='#5555FF'>=</font> temp.parent;
        temp.parent <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;  


        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>tree_root <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
            tree_root <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>temp;
        <font color='#0000FF'>else</font>
        <b>{</b>
            <font color='#009900'>// t is a left child
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
                t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>temp;
            <font color='#0000FF'>else</font>
                t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>temp;
        <b>}</b>
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>temp;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='remove_biggest_element_in_tree'></a>remove_biggest_element_in_tree</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t,
        domain<font color='#5555FF'>&amp;</font> d,
        range<font color='#5555FF'>&amp;</font> r
    <font face='Lucida Console'>)</font> 
    <b>{</b>

        node<font color='#5555FF'>*</font> next <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
        node<font color='#5555FF'>*</font> child;  <font color='#009900'>// the child node of the one we will slice out
</font>
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>next <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
        <b>{</b>
            <font color='#009900'>// need to determine if t is a right or left child
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
                child <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
            <font color='#0000FF'>else</font>
                child <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;

            <font color='#009900'>// update tree_root if necessary
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> tree_root<font face='Lucida Console'>)</font>
                tree_root <font color='#5555FF'>=</font> child;
        <b>}</b>
        <font color='#0000FF'>else</font>
        <b>{</b>
            <font color='#009900'>// find the least node
</font>            <font color='#0000FF'>do</font> 
            <b>{</b>
                t <font color='#5555FF'>=</font> next;
                next <font color='#5555FF'>=</font> next<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
            <b>}</b> <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font>next <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>;
            <font color='#009900'>// t is a right child
</font>            child <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;

        <b>}</b>
        
        <font color='#009900'>// swap the item from this node into d and r
</font>        <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>d,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d<font face='Lucida Console'>)</font>;
        <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>r,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r<font face='Lucida Console'>)</font>;

        <font color='#009900'>// plug hole right by removing this node
</font>        child<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;

        <font color='#009900'>// keep the red-black properties true
</font>        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
            <font color='#BB00BB'>fix_after_remove</font><font face='Lucida Console'>(</font>child<font face='Lucida Console'>)</font>;

        <font color='#009900'>// free the memory for this removed node
</font>        pool.<font color='#BB00BB'>deallocate</font><font face='Lucida Console'>(</font>t<font face='Lucida Console'>)</font>;        
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>bool</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='remove_least_element_in_tree'></a>remove_least_element_in_tree</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t,
        domain<font color='#5555FF'>&amp;</font> d,
        range<font color='#5555FF'>&amp;</font> r
    <font face='Lucida Console'>)</font> 
    <b>{</b>

        node<font color='#5555FF'>*</font> next <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
        node<font color='#5555FF'>*</font> child;  <font color='#009900'>// the child node of the one we will slice out
</font>
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>next <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
        <b>{</b>
            <font color='#009900'>// need to determine if t is a left or right child
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
                child <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
            <font color='#0000FF'>else</font>
                child <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;

            <font color='#009900'>// update tree_root if necessary
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> tree_root<font face='Lucida Console'>)</font>
                tree_root <font color='#5555FF'>=</font> child;
        <b>}</b>
        <font color='#0000FF'>else</font>
        <b>{</b>
            <font color='#009900'>// find the least node
</font>            <font color='#0000FF'>do</font> 
            <b>{</b>
                t <font color='#5555FF'>=</font> next;
                next <font color='#5555FF'>=</font> next<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
            <b>}</b> <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font>next <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>;
            <font color='#009900'>// t is a left child
</font>            child <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;

        <b>}</b>
        
        <font color='#009900'>// swap the item from this node into d and r
</font>        <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>d,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d<font face='Lucida Console'>)</font>;
        <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>r,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r<font face='Lucida Console'>)</font>;

        <font color='#009900'>// plug hole left by removing this node
</font>        child<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;

        <font color='#009900'>// keep the red-black properties true
</font>        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
            <font color='#BB00BB'>fix_after_remove</font><font face='Lucida Console'>(</font>child<font face='Lucida Console'>)</font>;

        <font color='#0000FF'><u>bool</u></font> rvalue <font color='#5555FF'>=</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> current_element<font face='Lucida Console'>)</font>;
        <font color='#009900'>// free the memory for this removed node
</font>        pool.<font color='#BB00BB'>deallocate</font><font face='Lucida Console'>(</font>t<font face='Lucida Console'>)</font>;        
        <font color='#0000FF'>return</font> rvalue;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='add_to_tree'></a>add_to_tree</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t,
        domain<font color='#5555FF'>&amp;</font> d,
        range<font color='#5555FF'>&amp;</font> r
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        <font color='#009900'>// parent of the current node
</font>        node<font color='#5555FF'>*</font> parent;

        <font color='#009900'>// find a place to add node
</font>        <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font><font color='#979000'>true</font><font face='Lucida Console'>)</font>
        <b>{</b>
            parent <font color='#5555FF'>=</font> t;
            <font color='#009900'>// if item should be put on the left then go left
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font><font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>d , t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d<font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
            <b>{</b>
                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
                <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                <b>{</b>
                    t <font color='#5555FF'>=</font> parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> pool.<font color='#BB00BB'>allocate</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
                    <font color='#0000FF'>break</font>;
                <b>}</b>
            <b>}</b>
            <font color='#009900'>// if item should be put on the right then go right
</font>            <font color='#0000FF'>else</font>
            <b>{</b>
                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
                <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                <b>{</b>
                    t <font color='#5555FF'>=</font> parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> pool.<font color='#BB00BB'>allocate</font><font face='Lucida Console'>(</font><font face='Lucida Console'>)</font>;
                    <font color='#0000FF'>break</font>;
                <b>}</b>
            <b>}</b>
        <b>}</b>

        <font color='#009900'>// t is now the node where we will add item and
</font>        <font color='#009900'>// parent is the parent of t
</font>
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> parent;
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> NIL;
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> NIL;
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> red;
        <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d,d<font face='Lucida Console'>)</font>;
        <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r,r<font face='Lucida Console'>)</font>;


        <font color='#009900'>// keep the red-black properties true
</font>        <font color='#BB00BB'>fix_after_add</font><font face='Lucida Console'>(</font>t<font face='Lucida Console'>)</font>;
    <b>}</b> 

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='remove_from_tree'></a>remove_from_tree</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t,
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d,
        domain<font color='#5555FF'>&amp;</font> d_copy,
        range<font color='#5555FF'>&amp;</font> r
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font><font color='#979000'>true</font><font face='Lucida Console'>)</font>
        <b>{</b>
            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font> <font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>d , t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d<font face='Lucida Console'>)</font> <font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// if item is on the left then look in left
</font>                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
            <b>}</b>
            <font color='#0000FF'>else</font> <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font><font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d , d<font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// if item is on the right then look in right
</font>                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>
                <font color='#009900'>// found the node we want to remove
</font>
                <font color='#009900'>// swap out the item into d_copy and r
</font>                <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>d_copy,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d<font face='Lucida Console'>)</font>;
                <font color='#BB00BB'>exchange</font><font face='Lucida Console'>(</font>r,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r<font face='Lucida Console'>)</font>;

                <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                <b>{</b>
                    <font color='#009900'>// if there is no left subtree
</font>
                    node<font color='#5555FF'>*</font> parent <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;
                    
                    <font color='#009900'>// plug hole with right subtree
</font>

                    <font color='#009900'>// if t is on the left
</font>                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
                        parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;  
                    <font color='#0000FF'>else</font>
                        parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
                    t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> parent;

                    <font color='#009900'>// update tree_root if necessary
</font>                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> tree_root<font face='Lucida Console'>)</font>
                        tree_root <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;

                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
                        <font color='#BB00BB'>fix_after_remove</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font face='Lucida Console'>)</font>;

                    <font color='#009900'>// delete old node
</font>                    pool.<font color='#BB00BB'>deallocate</font><font face='Lucida Console'>(</font>t<font face='Lucida Console'>)</font>;  
                <b>}</b>
                <font color='#0000FF'>else</font> <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                <b>{</b>
                    <font color='#009900'>// if there is no right subtree
</font>
                    node<font color='#5555FF'>*</font> parent <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;
                    
                    <font color='#009900'>// plug hole with left subtree
</font>                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
                        parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;  
                    <font color='#0000FF'>else</font>
                        parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
                    t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> parent;

                    <font color='#009900'>// update tree_root if necessary
</font>                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> tree_root<font face='Lucida Console'>)</font>
                        tree_root <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;

                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
                        <font color='#BB00BB'>fix_after_remove</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font face='Lucida Console'>)</font>;

                    <font color='#009900'>// delete old node
</font>                    pool.<font color='#BB00BB'>deallocate</font><font face='Lucida Console'>(</font>t<font face='Lucida Console'>)</font>;
                <b>}</b>
                <font color='#0000FF'>else</font>
                <b>{</b>
                    <font color='#009900'>// if there is both a left and right subtree
</font>                    <font color='#009900'>// get an element to fill this node now that its been swapped into 
</font>                    <font color='#009900'>// item_copy
</font>                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font><font color='#BB00BB'>remove_least_element_in_tree</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r<font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
                    <b>{</b>
                        <font color='#009900'>// the node removed was the one pointed to by current_element so we
</font>                        <font color='#009900'>// need to update it so that it points to the right spot.
</font>                        current_element <font color='#5555FF'>=</font> t;
                    <b>}</b>
                <b>}</b>

                <font color='#009900'>// quit loop
</font>                <font color='#0000FF'>break</font>;
            <b>}</b>
        <b>}</b>
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='remove_from_tree'></a>remove_from_tree</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t,
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font><font color='#979000'>true</font><font face='Lucida Console'>)</font>
        <b>{</b>
            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font> <font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>d , t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d<font face='Lucida Console'>)</font> <font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// if item is on the left then look in left
</font>                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
            <b>}</b>
            <font color='#0000FF'>else</font> <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font><font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d , d<font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// if item is on the right then look in right
</font>                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>
                <font color='#009900'>// found the node we want to remove
</font>

                <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                <b>{</b>
                    <font color='#009900'>// if there is no left subtree
</font>
                    node<font color='#5555FF'>*</font> parent <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;
                    
                    <font color='#009900'>// plug hole with right subtree
</font>

                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
                        parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;  
                    <font color='#0000FF'>else</font>
                        parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
                    t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> parent;

                    <font color='#009900'>// update tree_root if necessary
</font>                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> tree_root<font face='Lucida Console'>)</font>
                        tree_root <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;

                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
                        <font color='#BB00BB'>fix_after_remove</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font face='Lucida Console'>)</font>;

                    <font color='#009900'>// delete old node
</font>                    pool.<font color='#BB00BB'>deallocate</font><font face='Lucida Console'>(</font>t<font face='Lucida Console'>)</font>;  
                <b>}</b>
                <font color='#0000FF'>else</font> <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
                <b>{</b>
                    <font color='#009900'>// if there is no right subtree
</font>
                    node<font color='#5555FF'>*</font> parent <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;
                    
                    <font color='#009900'>// plug hole with left subtree
</font>                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
                        parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;  
                    <font color='#0000FF'>else</font>
                        parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
                    t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font> parent;

                    <font color='#009900'>// update tree_root if necessary
</font>                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> tree_root<font face='Lucida Console'>)</font>
                        tree_root <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;

                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
                        <font color='#BB00BB'>fix_after_remove</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font face='Lucida Console'>)</font>;

                    <font color='#009900'>// delete old node
</font>                    pool.<font color='#BB00BB'>deallocate</font><font face='Lucida Console'>(</font>t<font face='Lucida Console'>)</font>;
                <b>}</b>
                <font color='#0000FF'>else</font>
                <b>{</b>
                    <font color='#009900'>// if there is both a left and right subtree
</font>                    <font color='#009900'>// get an element to fill this node now that its been swapped into 
</font>                    <font color='#009900'>// item_copy
</font>                    <font color='#BB00BB'>remove_least_element_in_tree</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d,t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r<font face='Lucida Console'>)</font>;

                <b>}</b>

                <font color='#009900'>// quit loop
</font>                <font color='#0000FF'>break</font>;
            <b>}</b>
        <b>}</b>
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    range<font color='#5555FF'>*</font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='return_reference'></a>return_reference</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t,
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
    <font face='Lucida Console'>)</font> 
    <b>{</b>
        <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
        <b>{</b>
            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font> <font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>d , t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d <font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// if item is on the left then look in left
</font>                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
            <b>}</b>
            <font color='#0000FF'>else</font> <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font><font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d , d<font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// if item is on the right then look in right
</font>                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>
                <font color='#009900'>// if it's found then return a reference to it
</font>                <font color='#0000FF'>return</font> <font color='#5555FF'>&amp;</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r<font face='Lucida Console'>)</font>;
            <b>}</b>
        <b>}</b>
        <font color='#0000FF'>return</font> <font color='#979000'>0</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'>const</font> range<font color='#5555FF'>*</font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='return_reference'></a>return_reference</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> node<font color='#5555FF'>*</font> t,
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
        <b>{</b>
            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font> <font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>d , t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d<font face='Lucida Console'>)</font> <font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// if item is on the left then look in left
</font>                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
            <b>}</b>
            <font color='#0000FF'>else</font> <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font><font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d , d<font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// if item is on the right then look in right
</font>                t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>
                <font color='#009900'>// if it's found then return a reference to it
</font>                <font color='#0000FF'>return</font> <font color='#5555FF'>&amp;</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>r<font face='Lucida Console'>)</font>;
            <b>}</b>
        <b>}</b>
        <font color='#0000FF'>return</font> <font color='#979000'>0</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='fix_after_add'></a>fix_after_add</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t
    <font face='Lucida Console'>)</font>
    <b>{</b>

        <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> red<font face='Lucida Console'>)</font>
        <b>{</b>
            node<font color='#5555FF'>&amp;</font> grandparent <font color='#5555FF'>=</font> <font color='#5555FF'>*</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font face='Lucida Console'>)</font>;

            <font color='#009900'>// if both t's parent and its sibling are red 
</font>            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>grandparent.left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> grandparent.right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color<font face='Lucida Console'>)</font>
            <b>{</b>
                grandparent.color <font color='#5555FF'>=</font> red;
                grandparent.left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                grandparent.right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                t <font color='#5555FF'>=</font> <font color='#5555FF'>&amp;</font>grandparent;
            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>
                <font color='#009900'>// if t is a left child
</font>                <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font face='Lucida Console'>)</font>
                <b>{</b>
                    <font color='#009900'>// if t's parent is a left child
</font>                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font><font color='#5555FF'>=</font> grandparent.left<font face='Lucida Console'>)</font>
                    <b>{</b>
                        grandparent.color <font color='#5555FF'>=</font> red;
                        grandparent.left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                        <font color='#BB00BB'>rotate_right</font><font face='Lucida Console'>(</font><font color='#5555FF'>&amp;</font>grandparent<font face='Lucida Console'>)</font>;
                    <b>}</b>
                    <font color='#009900'>// if t's parent is a right child
</font>                    <font color='#0000FF'>else</font>
                    <b>{</b>
                        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                        grandparent.color <font color='#5555FF'>=</font> red;
                        <font color='#BB00BB'>double_rotate_left</font><font face='Lucida Console'>(</font><font color='#5555FF'>&amp;</font>grandparent<font face='Lucida Console'>)</font>;
                    <b>}</b>
                <b>}</b>
                <font color='#009900'>// if t is a right child
</font>                <font color='#0000FF'>else</font>
                <b>{</b>
                    <font color='#009900'>// if t's parent is a left child
</font>                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent <font color='#5555FF'>=</font><font color='#5555FF'>=</font> grandparent.left<font face='Lucida Console'>)</font>
                    <b>{</b>
                        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                        grandparent.color <font color='#5555FF'>=</font> red;                        
                        <font color='#BB00BB'>double_rotate_right</font><font face='Lucida Console'>(</font><font color='#5555FF'>&amp;</font>grandparent<font face='Lucida Console'>)</font>;
                    <b>}</b>
                    <font color='#009900'>// if t's parent is a right child
</font>                    <font color='#0000FF'>else</font>
                    <b>{</b>
                        grandparent.color <font color='#5555FF'>=</font> red;
                        grandparent.right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                        <font color='#BB00BB'>rotate_left</font><font face='Lucida Console'>(</font><font color='#5555FF'>&amp;</font>grandparent<font face='Lucida Console'>)</font>;
                    <b>}</b>
                <b>}</b>
                <font color='#0000FF'>break</font>;
            <b>}</b>
        <b>}</b>
        tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
    <b>}</b>       

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>void</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='fix_after_remove'></a>fix_after_remove</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t
    <font face='Lucida Console'>)</font>
    <b>{</b>

        <font color='#0000FF'>while</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>!</font><font color='#5555FF'>=</font> tree_root <font color='#5555FF'>&amp;</font><font color='#5555FF'>&amp;</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
        <b>{</b>
            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left <font color='#5555FF'>=</font><font color='#5555FF'>=</font> t<font face='Lucida Console'>)</font>
            <b>{</b>
                node<font color='#5555FF'>*</font> sibling <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
                <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> red<font face='Lucida Console'>)</font>
                <b>{</b>
                    sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                    t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> red;
                    <font color='#BB00BB'>rotate_left</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font face='Lucida Console'>)</font>;
                    sibling <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
                <b>}</b>

                <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black <font color='#5555FF'>&amp;</font><font color='#5555FF'>&amp;</font> sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
                <b>{</b>
                    sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> red;
                    t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;
                <b>}</b>
                <font color='#0000FF'>else</font>
                <b>{</b>
                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
                    <b>{</b>
                        sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                        sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> red;
                        <font color='#BB00BB'>rotate_right</font><font face='Lucida Console'>(</font>sibling<font face='Lucida Console'>)</font>;
                        sibling <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right;
                    <b>}</b>

                    sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color;
                    t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                    sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                    <font color='#BB00BB'>rotate_left</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font face='Lucida Console'>)</font>;
                    t <font color='#5555FF'>=</font> tree_root;

                <b>}</b>


            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>

                node<font color='#5555FF'>*</font> sibling <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
                <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> red<font face='Lucida Console'>)</font>
                <b>{</b>
                    sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                    t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> red;
                    <font color='#BB00BB'>rotate_right</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font face='Lucida Console'>)</font>;
                    sibling <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
                <b>}</b>

                <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black <font color='#5555FF'>&amp;</font><font color='#5555FF'>&amp;</font> sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
                <b>{</b>
                    sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> red;
                    t <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent;
                <b>}</b>
                <font color='#0000FF'>else</font>
                <b>{</b>
                    <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font><font color='#5555FF'>=</font> black<font face='Lucida Console'>)</font>
                    <b>{</b>
                        sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                        sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> red;
                        <font color='#BB00BB'>rotate_left</font><font face='Lucida Console'>(</font>sibling<font face='Lucida Console'>)</font>;
                        sibling <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left;
                    <b>}</b>

                    sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color;
                    t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                    sibling<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
                    <font color='#BB00BB'>rotate_right</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>parent<font face='Lucida Console'>)</font>;
                    t <font color='#5555FF'>=</font> tree_root;

                <b>}</b>


            <b>}</b>

        <b>}</b>
        t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>color <font color='#5555FF'>=</font> black;
    
    <b>}</b>         

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>short</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='tree_height'></a>tree_height</b> <font face='Lucida Console'>(</font>
        node<font color='#5555FF'>*</font> t
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>t <font color='#5555FF'>=</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
            <font color='#0000FF'>return</font> <font color='#979000'>0</font>;

        <font color='#0000FF'><u>short</u></font> height1 <font color='#5555FF'>=</font> <font color='#BB00BB'>tree_height</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font face='Lucida Console'>)</font>;
        <font color='#0000FF'><u>short</u></font> height2 <font color='#5555FF'>=</font> <font color='#BB00BB'>tree_height</font><font face='Lucida Console'>(</font>t<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font face='Lucida Console'>)</font>;        
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>height1 <font color='#5555FF'>&gt;</font> height2<font face='Lucida Console'>)</font>
            <font color='#0000FF'>return</font> height1 <font color='#5555FF'>+</font> <font color='#979000'>1</font>;
        <font color='#0000FF'>else</font>
            <font color='#0000FF'>return</font> height2 <font color='#5555FF'>+</font> <font color='#979000'>1</font>;
    <b>}</b>       

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
    <font color='#0000FF'>template</font> <font color='#5555FF'>&lt;</font>
        <font color='#0000FF'>typename</font> domain,
        <font color='#0000FF'>typename</font> range,
        <font color='#0000FF'>typename</font> mem_manager,
        <font color='#0000FF'>typename</font> compare
        <font color='#5555FF'>&gt;</font>
    <font color='#0000FF'><u>unsigned</u></font> <font color='#0000FF'><u>long</u></font> binary_search_tree_kernel_2<font color='#5555FF'>&lt;</font>domain,range,mem_manager,compare<font color='#5555FF'>&gt;</font>::
    <b><a name='get_count'></a>get_count</b> <font face='Lucida Console'>(</font>
        <font color='#0000FF'>const</font> domain<font color='#5555FF'>&amp;</font> d,
        node<font color='#5555FF'>*</font> tree_root
    <font face='Lucida Console'>)</font> <font color='#0000FF'>const</font>
    <b>{</b>
        <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font>tree_root <font color='#5555FF'>!</font><font color='#5555FF'>=</font> NIL<font face='Lucida Console'>)</font>
        <b>{</b>
            <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font><font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>d , tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d<font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// go left
</font>                <font color='#0000FF'>return</font> <font color='#BB00BB'>get_count</font><font face='Lucida Console'>(</font>d,tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font face='Lucida Console'>)</font>;                
            <b>}</b>
            <font color='#0000FF'>else</font> <font color='#0000FF'>if</font> <font face='Lucida Console'>(</font><font color='#BB00BB'>comp</font><font face='Lucida Console'>(</font>tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>d , d<font face='Lucida Console'>)</font><font face='Lucida Console'>)</font>
            <b>{</b>
                <font color='#009900'>// go right
</font>                <font color='#0000FF'>return</font> <font color='#BB00BB'>get_count</font><font face='Lucida Console'>(</font>d,tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font face='Lucida Console'>)</font>;
            <b>}</b>
            <font color='#0000FF'>else</font>
            <b>{</b>
                <font color='#009900'>// go left and right to look for more matches
</font>                <font color='#0000FF'>return</font>   <font color='#BB00BB'>get_count</font><font face='Lucida Console'>(</font>d,tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>left<font face='Lucida Console'>)</font> 
                       <font color='#5555FF'>+</font> <font color='#BB00BB'>get_count</font><font face='Lucida Console'>(</font>d,tree_root<font color='#5555FF'>-</font><font color='#5555FF'>&gt;</font>right<font face='Lucida Console'>)</font> 
                       <font color='#5555FF'>+</font> <font color='#979000'>1</font>;
            <b>}</b>
        <b>}</b>
        <font color='#0000FF'>return</font> <font color='#979000'>0</font>;
    <b>}</b>

<font color='#009900'>// ----------------------------------------------------------------------------------------
</font>
<b>}</b>

<font color='#0000FF'>#endif</font> <font color='#009900'>// DLIB_BINARY_SEARCH_TREE_KERNEl_2_
</font>

</pre></body></html>